package ltd.smallwang;

/**
 * @author justd
 * @date 2024-11-03 20:06
 */
public class Leetcode0209 {

  public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int sum = 0;
    int result = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
      sum += nums[right];
      if (sum >= target) {
        while (sum - nums[left] >= target && left <= right) {
          sum -= nums[left];
          left++;
        }
        result = Math.min(result, right - left + 1);
      }
    }
    return result == Integer.MAX_VALUE ? 0 : result;
  }

  /**
   * 使用暴力算法寻找数组中子数组的最小长度，使得子数组的和至少达到目标值 如果找不到满足条件的子数组，则返回0 此方法首先计算整个数组的和，如果这个和都小于目标值，则不可能找到满足条件的子数组
   * 如果和大于等于目标值，则调用getMinLength方法尝试找到满足条件的最小子数组长度
   *
   * @param target 目标值，子数组的和至少需要达到这个值
   * @param nums   输入的整数数组
   * @return 满足条件的子数组的最小长度，如果不存在则返回0
   */
  @SuppressWarnings("unused")
  private int violentAlgorithm(int target, int[] nums) {
    int sum = 0;
    // 遍历数组，计算所有元素的总和
    for (int num : nums) {
      sum += num;
    }
    // 如果整个数组的和小于目标值，则不可能找到满足条件的子数组，返回0
    if (sum < target) {
      return 0;
    }
    // 调用getMinLength方法尝试找到满足条件的最小子数组长度
    return getMinLength(target, nums, 0, nums.length - 1, sum);
  }


  private int getMinLength(int target, int[] nums, int left, int right, int sum) {
    if (sum - nums[left] < target && sum - nums[right] < target) {
      return right - left + 1;
    }
    int leftMinLen = Integer.MAX_VALUE;
    int rightMinLen = Integer.MAX_VALUE;
    if (sum - nums[left] >= target) {
      leftMinLen = getMinLength(target, nums, left + 1, right, sum - nums[left]);
    }
    if (sum - nums[right] >= target) {
      rightMinLen = getMinLength(target, nums, left, right - 1, sum - nums[right]);
    }
    return Math.min(leftMinLen, rightMinLen);
  }
}
